home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group94c.txt / 000000_icon-group-sender _Wed Dec 7 22:16:49 1994.msg next >
Internet Message Format  |  1995-02-09  |  1KB
  1. Received: by cheltenham.cs.arizona.edu; Wed, 7 Dec 1994 17:07:13 MST
  2. To: icon-group-l@cs.arizona.edu
  3. Date: Wed, 7 Dec 1994 22:16:49 GMT
  4. From: vorbeck@cs.sfu.ca (Martin Vorbeck)
  5. Message-Id: <1994Dec7.221649.10939@cs.sfu.ca>
  6. Organization: Faculty of Applied Science, Simon Fraser University
  7. Sender: icon-group-request@cs.arizona.edu
  8. Subject: [Q] Algorithm for Regexp Subsumption
  9. Errors-To: icon-group-errors@cs.arizona.edu
  10.  
  11. Hi,
  12.  
  13.   are there any algorithms out there for checking whether a regular
  14. expression subsumes another one, ie L(E1) is a subset of L(E2)? I have a
  15. "brute-force" solution along these lines:
  16.  
  17. 1. Compute equivalent finite automatas A1 (resp A2) for E1 (resp E2).
  18. 2. Compute A3 = A1 intersected with the complement of A2.
  19. 3. Test L(A3) = empty  ==>  E2 subsumes E1.
  20.  
  21. But I wonder if this couldn't be done directly on the regular
  22. expressions E1 and E2? As an aside note, just a reminder that regexp
  23. inequivalence is NP-Hard (Garey & Johnson), so I don't expect anything
  24. extremely efficient. 
  25.  
  26.   Any help would be very much appreciated.
  27.  
  28. Please Email any replies to
  29.     vorbeck@cs.sfu.ca
  30. as I don't usually read these newsgroups.
  31.  
  32. Thanks !
  33.  
  34. -- Martin Vorbeck
  35.  
  36.